#include<iostream>
#include<stdio.h>
#include<conio.h>

using namespace std;

typedef struct Vat
{
        float kichthuoc;
        int check;       
};

void SapXep(Vat a[100], int n)
{
     for(int i=0;i<n;i++)
             for(int j=0;j<n;j++)
                     if(a[i].kichthuoc > a[j].kichthuoc)
                     {
                           Vat tam=a[i];
                           a[i]=a[j];
                           a[j]=tam;             
                     }    
}

void Xuat(Vat a[100], int n)
{
     for(int i=0;i<n;i++)
     {
             cout<<"\n";
             cout<<"San pham thu "<<i<<" co kich thuoc la "<<a[i].kichthuoc;        
     }     
}

int main()
{
     int n;
     float T;
     Vat a[100];
     Vat tui[100];
     cout<<"\nNhap so san pham trong cua hang: ";cin>>n;
     
     
     cout<<"\nNhap kich thuoc cua tui T: ";cin>>T;
     cout<<"\n Hay nhap kich thuoc san pham tung san pham";
     cout<<"\n (Luu y chi nhap vao kich thuoc san pham tu 1 den "<<T-1 <<") ";
     
     
         for(int i=0;i<n;i++)
         {
                 cout<<"\n\nNhap vao kich thuoc cua san pham thu "<<i<<" : ";cin>>a[i].kichthuoc;       
                 a[i].check=0;
         } 
         
         
     Xuat(a,n);
     cout<<"\n";
     SapXep(a,n);
     cout<<"\nCac San Pham sau khi sap xep giam dan theo kich thuoc la: ";
     Xuat(a,n);
     int dem=0;
     for(int i=0;i<n;i++)
             if(a[i].check==0)
             {
                              
              dem++;
              cout<<"\n\nTui thu "<<dem<<":"<<a[i].kichthuoc<<" ";
              //tui[dem]=a[i];
              
              float tong = a[i].kichthuoc;
              a[i].check=1;
              
              for(int j=1;j<n;j++)
              {
                      
              if(a[j].check==0 && tong+a[j].kichthuoc<=T)
              {
                  tong=tong+a[j].kichthuoc;
                 // if(tong<=T)
                 // {
                      a[j].check=1;                      
                 // }
                 cout<<a[j].kichthuoc<<" ";
              }
              
              }
             }
     cout<<"\n\nSo tui it nhat can lay la :"<<dem;
        
     getch();
     
     return 0;          
}